def insertion(my_list):
for i in range(1,len(my_list)):
k = i
while i>0 and my_list[i] < my_list[i-1]:
my_list[i],my_list[i-1]=my_list[i-1],my_list[i]
i=i-1
print(my_list)
print('sorted',my_list)
list1=[4,6,3,9,2]
print('Unsorted',list1)
insertion(list1)
Unsorted [4, 6, 3, 9, 2] [4, 6, 3, 9, 2] [3, 4, 6, 9, 2] [3, 4, 6, 9, 2] [2, 3, 4, 6, 9] sorted [2, 3, 4, 6, 9]
def selection(my_list):
for i in range(0,len(my_list)-1):
for j in range(i+1,len(my_list)):
if my_list[i] > my_list[j]:
my_list[i],my_list[j]=my_list[j],my_list[i]
print('sorted:',my_list)
list1=[6,8,3,5,9,10,7,2,4,1]
print('unsorted',list1)
selection(list1)
unsorted [6, 8, 3, 5, 9, 10, 7, 2, 4, 1] sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
def bubble(my_list):
for i in range(0,len(my_list)):
for j in range(0,len(my_list)-1):
if my_list[j] > my_list[j+1]:
my_list[j],my_list[j+1]= my_list[j+1],my_list[j]
print('sorted:',my_list)
list2=[7,8,2,0,1]
print('unsorted:',list2)
bubble(list2)
unsorted: [7, 8, 2, 0, 1] sorted: [0, 1, 2, 7, 8]
def mergesort(list1):
if len(list1)>1:
mid = len(list1)//2
left_list = list1[:mid]
right_list = list1[mid:]
mergesort(left_list)
mergesort(right_list)
i=0
j=0
k=0
while i<len(left_list) and j<len(right_list):
if left_list[i] < right_list[j]:
list1[k] = left_list[i]
i=i+1
k=k+1
else:
list1[k] = right_list[j]
j=j+1
k=k+1
while i<len(left_list):
list1[k]=left_list[i]
i=i+1
k=k+1
while j<len(right_list):
list1[k] = right_list[j]
j=j+1
k=k+1
list2=[7,8,2,0,1]
print('unsorted:',list2)
mergesort(list2)
print('sorted list',list2)
unsorted: [7, 8, 2, 0, 1] sorted list [0, 1, 2, 7, 8]
# Easy way but not efficient way
def quick(list1):
if len(list1) <= 1:
return list1
else:
pivot=list1.pop()
greater=[]
lesser=[]
for i in list1:
if i > pivot:
greater.append(i)
else:
lesser.append(i)
return quick(lesser)+[pivot]+quick(greater)
li=[54,5,6,2,1,97,3]
print(quick(li))
[1, 2, 3, 5, 6, 54, 97]
#efficitent method
#"""three condition must be for quick sort"""
# 1] left <= right
# 2] left <= pivot if true then next left , if flase then stop and control goes to right side
# 3] right >= pivot if true the next right , if flase then stop and control goes for swapping
def pivot_place(list1,first,last):
pivot=list1[first]
left=first+1
right=last
while True:
while left <= right and list1[left] <= pivot :
left=left+1
while left <= right and list1[right] >= pivot:
right= right-1
if right < left :
break
else:
list1[left],list1[right]=list1[right],list1[left]
list1[first],list1[right]=list1[right],list1[first]
#print("1:",id(list1))
return right
def quicksort(list1,first,last):
if first < last:
p = pivot_place(list1,first,last)
print(list1)
#print("2:",id(list1))
#print(p)
quicksort(list1,first,p-1)
quicksort(list1,p+1,last)
li=[54,5,6,2,1,97,3]
n=len(li)
quicksort(li,0,n-1)
print("sorted List = ",li)
print("memory loc 3:",id(li))
[3, 5, 6, 2, 1, 54, 97] [2, 1, 3, 6, 5, 54, 97] [1, 2, 3, 6, 5, 54, 97] [1, 2, 3, 6, 5, 54, 97] [1, 2, 3, 6, 5, 54, 97] [1, 2, 3, 6, 5, 54, 97] [1, 2, 3, 5, 6, 54, 97] [1, 2, 3, 5, 6, 54, 97] [1, 2, 3, 5, 6, 54, 97] [1, 2, 3, 5, 6, 54, 97] [1, 2, 3, 5, 6, 54, 97] [1, 2, 3, 5, 6, 54, 97] sorted List = [1, 2, 3, 5, 6, 54, 97] memory loc 3: 2340241016704
def shell(list1):
gap=len(list1)//2
while gap > 0:
for index in range(gap,len(list1)):
current=list1[index]
position = index
while position >= gap and current < list1[position-gap]:
list1[position] =list1[position-gap]
position=position-gap
list1[position] = current
gap=gap//2
li=[54,5,6,2,1,97,3]
shell(li)
print(li)
[1, 2, 3, 5, 6, 54, 97]